#include<stdio.h>
#include<stdlib.h>

#ifndef NULL
#define NULL 0
#endif

typedef enum COLOR_ENUM{BLACK, RED}COLOR;

typedef struct NODE_TAG
{
    int key;
    int val;
    struct NODE_TAG *left;
    struct NODE_TAG *right;
    COLOR color;
}NODE;

/*        node                    x
         /   \     左旋转       /   \
        T1    x   --------->   node T3
        / \                   /   \
       T2 T3                 T1   T2
 */
NODE *leftRotate(NODE *node)
{ 
    NODE *x = node->right;
 
    /* 左旋转 */
    node->right = x->left;
    x->left = node;
 
    x->color = node->color;
    node->color = RED;
 
    return x;
}
 
/*       node                   x
        /   \     右旋转       /  \
       x    T2   ------->     y   node
      / \                         /  \
     y  T1                       T1  T2
*/
NODE *rightRotate(NODE *node)
{ 
    NODE *x = node->left;
 
    /* 右旋转 */
    node->left = x->right;
    x->right = node;
 
    x->color = node->color;
    node->color = RED;
 
    return x;
}
 
/* 颜色翻转 */
void flipColors(NODE *node)
{
    node->color = RED;
    node->left->color = BLACK;
    node->right->color = BLACK;
}

NODE *root;
int size;

void init()
{
    root = NULL;
    size = 0;
}

int isRed(NODE *node)
{
    if(node == NULL)
    {
        return BLACK;
    }
    return node->color;
}

void initNode(NODE *node, int key, int val)
{
    node->key = key;
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    node->color = RED;
}

NODE *addNode(NODE *node, int key, int val)
{
    if(node == NULL)
    {
        size++;
        node = malloc(sizeof(NODE));
        initNode(node, key, val);
        return node;
    }

    if(key < node->key)
    {
        node->left = addNode(node->left, key, val);
    }
    else if(key > node->key)
    {
        node->right = addNode(node->right, key, val);
    }
    else
    {
        node->val = val;
    }

    if(isRed(node->right) && !isRed(node->left))
    {
        node = leftRotate(node);
    }

    if(isRed(node->left) && isRed(node->left->left))
    {
        node = rightRotate(node);
    }

    if(isRed(node->left) && isRed(node->right))
    {
        flipColors(node);
    }
    
    return node;
}

/*
 向红黑树中添加新的元素
 */
void add(int key, int value)
{
    root = addNode(root, key, value);
    root->color = BLACK;
}

/*
 返回以 node 为根结点的红黑树中，key所在的节点
 */
NODE *getNode(NODE *node, int key)
{
    if (node == NULL)
        return NULL;

    if (key == node->key)
        return node;
    else if(key < node->key)
        return getNode(node->left, key);
    else if(key > node->key)
        return getNode(node->right, key);
}

int contains(int key)
{
    return getNode(root, key) != NULL;
}

int getVal(int key)
{
    NODE *node = getNode(root, key);
    
    if (node == NULL)
        return -999;
    return node->val;
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    init();
    int i = 0;
    for (; i < 10; i++)
    {
        add(i, arr[i]);
    }

    printf("Key:5, Val:%d /n" ,getVal(5));
    return 0;
}
